SUMMA subgraph matching in massive graphs.

Propagating Bug Fixes with Fast Subgraph Matching.

DESSIN Mining Dense Subgraph Patterns in a Single Graph.

Mining High%2DDimensional Data.

SAPPER Subgraph Indexing and Approximate Matching in Large Graphs.
With the emergence of new applications, e.g., computational biology, new software engineering techniques, social networks, etc., more data is in the form of graphs. Locating occurrences of a query graph in a large database graph is an important research topic. Due to the existence of noise (e.g., missing edges) in the large database graph, we investigate the problem of approximate subgraph indexing, i.e., finding the occurrences of a query graph in a large database graph with (possible) missing edges. The SAPPER method is proposed to solve this problem. Utilizing the hybrid neighborhood unit structures in the index, SAPPER takes advantage of pre-generated random spanning trees and a carefully designed graph enumeration order. Real and synthetic data sets are employed to demonstrate the efficiency and scalability of our approximate subgraph indexing method.
GADDI distance index based subgraph matching in biological networks.

RING An Integrated Method for Frequent Representative Subgraph Mining.

ARCS%2DMotif discovering correlated motifs from unaligned biological sequences.

Permu%2Dpattern discovery of mutable permutation patterns with proximity constraint.

RAM Randomized Approximate Graph Mining.

A gene pattern mining algorithm using interchangeable gene sets for prokaryotes.

Microarray data mining using landmark gene%2Dguided clustering.

Discovering Neglected Conditions in Software by Mining Dependence Graphs.

Introduction to special issue on bioinformatics.

Monkey Approximate Graph Mining Based on Spanning Trees.


TreePi A Novel Graph Indexing Method.


Data Mining in Bioinformatics %28BIOKDD%29.

PathFinder mining signal transduction pathway segments from protein%2Dprotein interaction networks.

Data Mining and Bioinformatics
Bioinformatics, the study and application of computational methods to life sciences data, is presently enjoying a surge of interest. The main reason for this welcome publicity is the nearing completion of the sequencing of the human genome and the anticipation that the knowledge derived from this process will have a great impact on modern medicine. The pharmaceutical industry, which expects to utilize the knowledge for new drug design, has a particular interest in bioinformatics. The structure of data...
TrajPattern Mining Sequential Patterns from Imprecise Trajectories of Mobile Objects.

Annotating proteins by mining protein interaction networks.
doi:10.1093/bioinformatics/btl221
A Biological Text Retrieval System Based on Background Knowledge and User Feedback.

ARCS an aggregated related column scoring scheme for aligned sequences.
Motivation: Biologists frequently align multiple biological sequences to determine consensus sequences and/or search for predominant residues and conserved regions. Particularly, determining conserved regions in an alignment is one of the most important activities. Since protein sequences are often several-hundred residues or longer, it is difficult to distinguish biologically important conserved regions (motifs or domains) from others. The widely used tools, Logos, Al2co, Confind, and the entropy-based method, often fail to highlight such regions. Thus a computational tool that can highlight biologically important regions accurately will be highly desired. Results: This paper presents a new scoring scheme ARCS (Aggregated Related Column Score) for aligned biological sequences. ARCS method considers not only the traditional character similarity measure but also column correlation. In an extensive experimental evaluation using 533 PROSITE patterns, ARCS is able to highlight the motif regions with up to 77.7 % accuracy corresponding to the top 3 peaks. Availability: The source code is available on
Efficient Classification across Multiple Database Relations A CrossMine Approach.

BIOKDD06 data mining in Bioinformatics.

Knowledge guided analysis of microarray data.

BIOKDD06 data mining in Bioinformatics.

Gene Teams with Relaxed Proximity Constraint.
Functionally related genes co-evolve, probably due to the strong selection pressure in evolution. Thus we expect that they are present in multiple genomes. Physical proximity among genes, known as gene team, is a very useful concept to discover functionally related genes in multiple genomes. However, there are also many gene sets that do not preserve physical proximity. In this paper, we generalized the gene team model, that looks for gene clusters in a physically clustered form, to multiple genome cases with relaxed constraint. We propose a novel hybrid pattern model that combines the set and the sequential pattern models. Our model searches for gene clusters with and/or without physical proximity constraint. This model is implemented and tested with 97 genomes (120 replicons). The result was analyzed to show the usefulness of our model. Especially, analysis of gene clusters that belong to B. subtilis and E. coli demonstrated that our model predicted many experimentally verified operons and functionally related clusters. Our program is fast enough to provide a sevice on the web at
Integrating Heterogeneous Microarray Data Sources Using Correlation Signatures.
Abstract. Microarrays are one of the latest breakthroughs in experimental molecular biology. Thousands of different research groups generate tens of thousands of microarray gene expression profiles based on different tissues, species, and conditions. Combining such vast amount of microarray data sets is an important and yet challenging problem. In this paper, we introduce a “correlation signature ” method that allows the coherent interpretation and integration of microarray data across disparate sources. The proposed algorithm first builds, for each gene (row) in a table, a correlation signature that captures the system-wide dependencies existing between the gene and the other genes within the table, and then compares the signatures across the tables for further analysis. We validate our framework with an experimental study using real microarray data sets, the result of which suggests that such an approach can be a viable solution for the microarray data integration and analysis problems. 1
Data Mining Techniques for Microarray Datasets.

Finding Representative Set from Massive Data.
In the information age, data is pervasive. In some applications, data explosion is a significant phenomenon. The massive data volume poses challenges to both human users and computers. In this project, we propose a new model for identifying representative set from a large database. A representative set is a special subset of the original dataset, which has three main characteristics: It is significantly smaller in size compared to the original dataset. It captures the most information from the original dataset compared to other subsets of the same size. It has low redundancy among the representatives it contains. We use informationtheoretic measures such as mutual information and relative entropy to measure the representativeness of the representative set. We first design a greedy algorithm and then present a heuristic algorithm that delivers much better performance. We run experiments on two real datasets and evaluate the effectiveness of our representative set in terms of coverage and accuracy. The experiments show that our representative set attains expected characteristics and captures information more efficiently. 1.
Searching for Related Objects in Relational Databases.
To discover knowledge or retrieve information from a relational database, a user often needs to find objects related to certain source objects. There are two main challenges in building an e#ective object search system: the huge amount of objects in the database and the large number of di#erent relationships between objects. In this paper we introduce Ross, an e#cient and accurate relational object search system. Ross accepts complex queries that enable users to specify the relationships among objects. To measure the relationships of join paths, Ross considers the di#erent semantics of di#erent joins, and combines both selectivity and lengths of join paths to measure their strengths. A novel approach is used to find the best join paths between relations, which converts the database schema into a graph, so that the shortest paths in the graph correspond to best join paths in the database. Ross uses a stream-based system architecture to handle complex queries containing logical operators, which can find the most related objects upon users&#039; requests. Comprehensive experiments are conducted to show the high scalability and e#ectiveness of Ross.
Survey of Biodata Analysis from a Data Mining Perspective.

Mining High%2DDimensional Data.

Making SVMs Scalable to Large Data Sets using Hierarchical Cluster Indexing.
Support vector machines (SVMs) have been promising methods for classification and regression analysis due to their solid mathematical foundations, which include two desirable properties: margin maximization and non-linear classification using kernels. However, despite these prominent properties, SVMs are usually not chosen for large-scale data mining problems because their training complexity is highly dependent on the data set size. Unlike traditional pattern recognition and machine learning, real-world data mining applications often involve huge num-bers of data records. Thus it is too expensive to perform multiple scans on the entire data set, and it is also infeasible to put the data set in memory. This paper presents a method, Clustering-Based SVM (CB-SVM), that maximizes the SVM performance for very large data sets given a limited amount of resource, e.g., memory. CB-SVM applies a hierarchical micro-clustering algorithm that scans the entire data set only once to provide an SVM with high quality samples. These samples carry statistical summaries of the data and maximize the benefit of learning. Our analyses show that the training complexity of CB-SVM is quadratically dependent on the number of support vectors, which is usually much less than that of the entire data set. Our experiments on synthetic and real-world data sets show that CB-SVM is highly scalable for very large data sets and very accurate in terms of classification. I.
A System of User%2DGuided Biological Literature Search Engine.

Guest Editors%27 Introduction Special Issue on Mining Biological Data.

An Improved Biclustering Method for Analyzing Gene Expression Profiles.

Biclustering in Gene Expression Data by Tendency.
The advent of DNA microarray technologies has revolutionized the experimental study of gene expression. Clustering is the most popular approach of analyzing gene expression data and has indeed proven to be successful in many applications. Our work focuses on discovering a subset of genes which exhibit similar expression patterns along a subset of conditions in the gene expression matrix. Specifically, we are looking for the Order Preserving clusters (OP-Cluster), in each of which a subset of genes induce a similar linear ordering along a subset of conditions. The pioneering work of the OPSM model[3], which enforces the strict order shared by the genes in a cluster, is included in our model as a special case. Our model is more robust than OPSM because similarly expressed conditions are allowed to form order equivalent groups and no restriction is placed on the order within a group. Guided by our model, we design and implement a deterministic algorithm, namely OPC-Tree, to discover OP-Clusters. Experimental study on two real datasets demonstrates the effectiveness of the algorithm in the application of tissue classification and cell cycle identification. In addition, a large percentage of OP-Clusters exhibit significant enrichment of one or more function categories, which implies that OP-Clusters indeed carry significant biological relevance.
Subspace Clustering for Microarray Data Analysis Multiple Criteria and Significance Assessment.

Gene Ontology Friendly Biclustering of Expression Profiles.
The soundness of clustering in the analysis of gene expression profiles and gene function prediction is based on the hypothesis that genes with similar expression profiles may imply strong correlations with their functions in the biological activities. Gene Ontology (GO) has become a well accepted standard in organizing gene function categories. Different gene function categories in GO can have very sophisticated relationships, such as ’part of ’ and ’overlapping’. Until now, no clustering algorithm can generate gene clusters within which the relationships can naturally reflect those of gene function categories in the GO hierarchy. The failure in resembling the relationships may reduce the confidence of clustering in gene function prediction. In this paper, we present a new clustering
Subspace Clustering for Microarray Data Analysis Multiple Criteria and Significance Assessment.

CrossMine Efficient Classification Across Multiple Database Relations.
Most of today&#039;s structured data is stored in relational databases. Such a database consists of multiple relations which are linked together conceptually via entity-relationship links in the design of relational database schemas. Multi-relational classification can be widely used in many disciplines, such as financial decision making, medical research, and geographical applications. However, most classification approaches only work on single &#034;flat&#034; data relations. It is usually difficult to convert multiple relations into a single flat relation without either introducing huge, undesirable &#034;universal relation&#034; or losing essential information. Previous works using Inductive Logic Programming approaches (recently also known as Relational Mining) have proven effective with high accuracy in multi-relational classification. Unfortunately, they suffer from poor scalability w.r.t. the number of relations and the number of attributes in databases.
CrossMine Efficient Classification Across Multiple Database Relations.
Most of today&#039;s structured data is stored in relational databases. Such a database consists of multiple relations which are linked together conceptually via entity-relationship links in the design of relational database schemas. Multi-relational classification can be widely used in many disciplines, such as financial decision making, medical research, and geographical applications. However, most classification approaches only work on single &#034;flat&#034; data relations. It is usually difficult to convert multiple relations into a single flat relation without either introducing huge, undesirable &#034;universal relation&#034; or losing essential information. Previous works using Inductive Logic Programming approaches (recently also known as Relational Mining) have proven effective with high accuracy in multi-relational classification. Unfortunately, they suffer from poor scalability w.r.t. the number of relations and the number of attributes in databases.
AGILE A General Approach to Detect Transitions in Evolving Data Streams.
In many applications such as e-commerce, system diagnosis and telecommunication services, data arrives in streams at a high speed. It is common that the underlying process generating the stream may change over time, either as a result of the fundamental evolution or in response to some external stimulus. Detecting these changes is a very challenging problem of great practical importance. The overall volume of the stream usually far exceeds the available main memory and access to the data stream is typically performed via a linear scan in ascending order of the indices of the records. In this paper, we propose a novel approach, AGILE, to monitor streaming data and to detect distinguishable transitions of the underlying processes. AGILE has many advantages over the traditional Hidden Markov Model, e.g., AGILE only requires one scan of the data.
SPIN mining maximal frequent subgraphs from graph databases.
One fundamental challenge for mining recurring subgraphs from semi-structured data sets is the overwhelming abundance of such patterns. In large graph databases, the total number of frequent subgraphs can become too large to allow a full enumeration using reasonable computational resources. In this paper, we propose a new algorithm that mines only maximal frequent subgraphs, i.e. subgraphs that are not a part of any other frequent subgraphs. This may exponentially decrease the size of the output set in the best case; in our experiments on practical data sets, mining maximal frequent subgraphs reduces the total number of mined patterns by two to three orders of magnitude. Our method first mines all frequent trees from a general graph database and then reconstructs all maximal subgraphs from the mined trees. Using two chemical structure benchmarks and a set of synthetic graph data sets, we demonstrate that, in addition to decreasing the output size, our algorithm can achieve a five-fold speed up over the current state-of-the-art subgraph mining algorithms.
Clustering moving objects.


A framework for ontology%2Ddriven subspace clustering.
Traditional clustering is a descriptive task that seeks to identify homogeneous groups of objects based on the values of their attributes. While domain knowledge is always the best way to justify clustering, few clustering algorithms have ever take domain knowledge into consideration. In this paper, the domain knowledge is represented by hierarchical ontology. We develop a framework by directly incorporating domain knowledge into clustering process, yielding a set of clusters with strong ontology implication. During the clustering process, ontology information is utilized to efficiently prune the exponential search space of the subspace clustering algorithms. Meanwhile, the algorithm generates automatical interpretation of the clustering result by mapping the natural hierarchical organized subspace clusters with significant categorical enrichment onto the ontology hierarchy. Our experiments on a set of gene expression data using gene ontology demonstrate that our pruning technique driven by ontology significantly improve the clustering performance with minimal degradation of the cluster quality. Meanwhile, many hierarchical organizations of gene clusters corresponding to a sub-hierarchies in gene ontology were also successfully captured.

Continuous K%2DNearest Neighbor Search for Moving Objects.
The paper describes a new method of continuously monitoring the    nearest neighbors of a given object in the mobile environment. Instead of monitoring all    nearest neighbors, we choose to monitor the    -th (nearest) neighbor since the necessary condition of changes in the KNN is the change   -th neighbor. In addition, rather than in the original space, we consider the moving objects in a transformed time-distance (TD) space, where each object is represented by a curve. A beach-line algorithm is developed to monitor the change of the    -th neighbor, which enables us to maintain the KNN incrementally. An extensive empirical study shows that the beach-line algorithm outperforms the most efficient existing algorithm by a wide margin, especially when    or    (the total number of objects) is large.
BASS Approximate Search on Large String Databases.
In this paper, we study the problem on how to build an index structure for large string databases to efficiently support various types of string matching without the necessity of mapping the substrings to a numerical space (e.g., string B-tree and MRS-index) nor the restriction of in-memory practice (e.g., suffix tree and suffix array). Towards this goal, we propose a new indexing scheme, BASS-tree, to efficiently support general approximate substring match (in terms of certain symbol substitutions and misalignments) in sublinear time on a large string database. The key idea behind the design is that all positions in each string are grouped recursively into a fully balanced tree according to the similarities of the subsequent segments starting at those positions. Each node is labeled with a regular expression that describes the commonality of the substrings indexed through the subtree. Any search can then be properly directed to the portion in the database with a high potential of matching quickly. With the BASS-tree in place, wild card(s) in the query pattern can also be handled in a seamless way. In addition, search of a long pattern can be decomposed into a series of searches of short segments followed by a process to join the results. It has been demonstrated in our experiments that the potential performance improvement brought by BASS-tree is in an order of magnitude over alternative methods.
Mining Surprising Periodic Patterns.
In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement,  information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure  property by the information gain measure and in turn provides an efficient solution to this problem. Empirical tests demonstrate the efficiency and the usefulness of the proposed model.
WAR Weighted Association Rules for Item Intensities.

Discovering High%2DOrder Periodic Patterns.
Discovery of periodic patterns in time series data has become an active research area with many applications. These patterns can be hierarchical in nature, where a higher level pattern may consist of repetitions of lower level patterns. Unfortunately, the presence of noise may prevent these higher level patterns from being recognized in the sense that two portions (of a data sequence) that support the same (high level) pattern may have di erent layouts of occurrences of basic symbols. There may not exist any common representation in terms of raw symbol combinations; and hence such (high level) pattern may not be expressed by any previous model (defined on raw symbols or symbol combinations) and would not be properly recognized by any existing method. In this paper, we propose a novel model, namely meta-pattern, to capture these high level patterns. As a more exible model, the number of potential meta-patterns could be very large. A substantial diculty lies on how to identify the proper pattern candidates. However, the well-known A priori property is not able to provide sufficient pruning power. A new property, namely component location property, is identified and used to conduct the candidate generation so that an ecient computation-based mining algorithm can be developed. Last but not least, we apply our algorithm to some real and synthetic sequences and some interesting patterns are discovered.
Discovering Compact and Highly Discriminative Features or Feature Combinations of Drug Activities Using Support Vector Machines.
Nowadays, high throughput experimental techniques make it feasible to examine and collect massive data at the molecular level. These data, typically mapped to a very high dimensional feature space, carry rich information about functionalities of certain chemical or biological entities and can be used to infer valuable knowledge for the purposes of classification and prediction. Typically, a small number of features or feature combinations may play determinant roles in functional discrimination. The identification of such features or feature combinations is of great importance. In this paper, we study the problem of discovering compact and highly discriminative features or feature combinations from a rich feature collection. We employ the support vector machine as the classification means and aim at finding compact feature combinations. Comparing to previous methods on feature selection, which identify features solely based on their individual roles in the classification, our method is able to identify minimal feature combinations that ultimately have determinant roles in a systematic fashion. Experimental study on drug activity data shows that our method can discover descriptors that are not necessarily significant individually but are most significant collectively.
Enhanced Biclustering on Expression Data.
molecular biology, which provide a powerful tool by which the expression patterns of thousands of genes can be monitored simultaneously and are already producing huge amount of valuable data. The concept of bicluster was introduced by Cheng and Church (2000) to capture the coherence of a subset of genes and a subset of conditions. A set of heuristic algorithms were also designed to either find one bicluster or a set of biclusters, which consist of iterations of masking null values and discovered biclusters, coarse and fine node deletion, node addition, and the inclusion of inverted data. These heuristics inevitably suffer from some serious drawback. The masking of null values and discovered biclusters with random numbers may result in the phenomenon of random interference which in turn impacts the discovery of high quality biclusters. To address this issue and to further accelerate the biclustering process, we generalize the model of bicluster to incorporate null values and propose a probabilistic algorithm (FLOC) that can discover a set of k possibly overlapping biclusters simultaneously. Furthermore, this algorithm can easily be extended to support additional features that suit different requirements at virtually little cost. Experimental study on the yeast gene expression data shows that the FLOC algorithm can offer substantial improvements over the previously proposed algorithm.
Discovering Compact and Highly Discriminative Features or Feature Combinations of Drug Activities Using Support Vector Machines.
Nowadays, high throughput experimental techniques make it feasible to examine and collect massive data at the molecular level. These data, typically mapped to a very high dimensional feature space, carry rich information about functionalities of certain chemical or biological entities and can be used to infer valuable knowledge for the purposes of classification and prediction. Typically, a small number of features or feature combinations may play determinant roles in functional discrimination. The identification of such features or feature combinations is of great importance. In this paper, we study the problem of discovering compact and highly discriminative features or feature combinations from a rich feature collection. We employ the support vector machine as the classification means and aim at finding compact feature combinations. Comparing to previous methods on feature selection, which identify features solely based on their individual roles in the classification, our method is able to identify minimal feature combinations that ultimately have determinant roles in a systematic fashion. Experimental study on drug activity data shows that our method can discover descriptors that are not necessarily significant individually but are most significant collectively.
Deliver Multimedia Streams with Flexible QoS via a Multicast DAG.

CLUSEQ Efficient and Effective Sequence Clustering.
Analyzing sequence data has become increasingly important recently in the area of biological sequences, text documents, web access logs, etc. In this paper, we investigate the problem of clustering sequences based on their structural features. As a widely recognized technique, clustering has proven to be very useful in detecting unknown object categories and revealing hidden correlations among objects. One difficulty that prevents clustering from being performed extensively on sequence data (in categorical domain) is the lack of an effective yet efficient similarity measure. Therefore, we propose a novel model (CLUSEQ) for sequence cluster by exploring significant statistical properties possessed by the sequences. The conditional probability distribution (CPD) of the next symbol given a preceding segment is derived and used to characterize sequence behavior and to support the similarity measure. A variation of the suffix tree, namely probabilistic suffix tree, is employed to organize (the significant portion of) the CPD in a concise way. A novel algorithm is devised to efficiently discover clusters with high quality and is able to automatically adjust the number of clusters to its optimal range via a unique combination of successive new cluster generation and cluster consolidation. The performance of CLUSEQ has been demonstrated via extensive experiments on several real and synthetic sequence databases. 1 
Dynamic Clustering of Evolving Streams with a Single Pass.

Classifying large data sets using SVMs with hierarchical clusters.

Carpenter finding closed patterns in long biological datasets.
new characteristics. These datasets typically contain a large number of columns and a small number of rows. For example, many gene expression datasets may contain 10,000100, 000 columns but only 100-1000 rows.
STAMP On Discovery of Statistically Important Pattern Repeats in Long Sequential Data.
In this paper, we focus on mining periodic patterns allowing some degree of imperfection in the form of random replacement from a perfect periodic pattern. In InfoMiner+, we proposed a new metric, namely generalized information gain, to identify patterns with events of vastly different occurrence frequencies and to adjust for the deviation from a pattern. In particular, a penalty is allowed to be associated with gaps between pattern occurrences. This is particularly useful in locating repeats in DNA sequences. In this paper, we present an effective mining algorithm, STAMP, to simultaneously mine significant patterns and the associated subsequences under the model of generalized information gain.
Mining Asynchronous Periodic Patterns in Time Series Data.
Periodicy detection in time series data is a challenging problem of great importance in many applications.
Recent Progress on Selected Topics in Database Research %2D A Report by Nine Young Chinese Researchers Working in the United States.

Towards Automatic Clustering of Protein Sequences.
Analyzing protein sequence data becomes increasingly important recently. Most previous work on this area has mainly focused on building classification models. In this paper, we investigate in the problem of automatic clustering of unlabeled protein sequences. As a widely recognized technique in statistics and computer science, clustering has been proven very useful in detecting unknown object categories and revealing hidden correlations among objects. One difficulty that prevents clustering from being performed directly on protein sequence is the lack of an effective similarity measure that can be computed efficiently. Therefore, we propose a novel model for protein sequence cluster by exploring significant statistical properties possessed by the sequences. The concept of imprecise probabilities are introduced to the original probabilistic suffix tree to monitor the convergence of the empirical measurement and to guide the clustering process. It has been demonstrated that the proposed method can successfully discover meaningful families without the necessity of learning models of different families from pre-labeled &#034;training data&#034;.
Accelerating Approximate Subsequence Search on Large Protein Sequence Databases.

A Framework Towards Efficient and Effective Sequence Clusterin.

delta%2DClusters Capturing Subspace Correlation in a Large Data Set.
Clustering has been an active research area of great practical importance for recent years. Most previous clustering models have focused on grouping objects with similar values on a (sub)set of dimensions (e.g., subspace cluster) and assumed that every object has an associated value on every dimension (e.g., bicluster). These existing cluster models may not always be adequate in capturing coherence exhibited among objects. Strong coherence may still exist among a set of objects (on a subset of attributes) even if they take quite different values on each attribute and the attribute values are not fully specified. This is very common in many applications including bio-informatics analysis as well as collaborative filtering analysis, where the data may be incomplete and subject to biases. In bio-informatics, a bicluster model has recently been proposed to capture coherence among a subset of the attributes. Here, we introduce a more general model, referred to as the ffi-cluster model, to capture coherence exhibited by a subset of objects on a subset of attributes, while allowing absent attribute values. A move-based algorithm (FLOC) is devised to efficiently produce a near-optimal clustering results. The ffi-cluster model takes the bicluster model as a special case, where the FLOC algorithm performs far superior to the bicluster algorithm. We demonstrate the correctness and efficiency of the ffi-cluster model and the FLOC algorithm on a number of real and synthetic data sets.
InfoMiner  Mining Partial Periodic Patterns with Gap Penalties.
In this paper, we focus on mining periodic patterns allowing some degree of imperfection in the form of random replacement from a perfect periodic pattern. Information gain was proposed to identify patterns with events of vastly different occurrence frequencies and adjust for the deviation from a pattern. However, it does not take any penalty if there exists some gap between the pattern occurrences. In many applications, e.g., bio-informatics, it is important to identify subsequences that a pattern repeats perfectly (or near perfectly). As a solution, we extend the information gain measure to include a penalty for gaps between pattern occurrences. We call this measure as generalized information gain. Furthermore, we want to find subsequence S    such that for a pattern P , the generalized information gain of P in S    is high. This is particularly useful in locating repeats in DNA sequences. In this paper, we developed an effective mining algorithm, InfoMiner+, to simultaneously mine significant patterns and the associated subsequences.
Efficient Filtering of Large DatasetA User%2DCentric Paradigm.

Clustering by pattern similarity in large data sets.
Clustering is the process of grouping a set of objects into classes of similar objects. Although definitions of similarity vary from one clustering model to another, in most of these models the concept of similarity is based on distances, e.g., Euclidean distance or cosine distance. In other words, similar objects are required to have close values on at least a set of dimensions. In this paper, we explore a more general type of similarity. Under the pCluster model we proposed, two objects are similar if they exhibit a coherent pattern on a subset of dimensions. For instance, in DNA microarray analysis, the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very much alike. Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks. E-commerce applications, such as collaborative filtering, can also benefit from the new model, which captures not only the closeness of values of certain leading indicators but also the closeness of (purchasing, browsing, etc.) patterns exhibited by the customers. Our paper introduces an effective algorithm to detect such clusters, and we perform tests on several real and synthetic data sets to show its effectiveness.
Mining long sequential patterns in a noisy environment.
many applications including computational biology study, consumer behavior analysis, system performance analysis, etc. In a noisy environment, an observed sequence may not accurately reflect the underlying behavior. For example, in a protein sequence, the amino acid N is likely to mutate to D with little impact to the biological function of the protein. It would be desirable if the occurrence of D in the observation can be related to a possible mutation from N in an appropriate manner. Unfortunately, the support measure (i.e., the number of occurrences) of a pattern does not serve this purpose. In this paper, we introduce the concept of compatibility matrix as the means to provide a probabilistic connection from the observation to the underlying true value. A new metric match is also proposed to capture the &#034;real support&#034; of a pattern which would be expected if a noise-free environment is assumed. In addition, in the context we address, a pattern could be very long. The standard pruning technique developed for the market basket problem may not work efficiently. As a result, a novel algorithm that combines statistical sampling and a new technique (namely border collapsing) is devised to discover long patterns in a minimal number of scans of the sequence database with sufficiently high confidence. Empirical results demonstrate the robustness of the match model (with respect to the noise) and the efficiency of the probabilistic algorithm.
TAR Temporal Association Rules on Evolving Numerical Attributes.
Data mining has been an area of increasing interests during recent years. The association rule discovery problem in particular has been widely studied. However, there are still some unresolved problems. For example, research on mining patterns in the evolution of numerical attributes is still lacking. This is both a challenging problem and one with significant practical application in business, science, and medicine. In this paper, we present a temporal association rule model for evolving numerical attributes. Metrics for qualifying a temporal association rule include the familiar measures of support and strength used in the traditional association rule mining and a new metric called density. The density metric not only gives us a way to extract the rules that best represent the data, but also provides an effective mechanism to prune the search space. An efficient algorithm is devised for mining temporal association rules, which utilizes all three thresholds (especially the strength) to prune the search space drastically. Moreover, the resulting rules are represented in a concise manner via rule sets to reduce the output size. Experimental results on real and synthetic data sets demonstrate the efficiency of our algorithm.
Meta%2Dpatterns Revealing Hidden Periodic Patterns.
Discovery of periodic patterns in time series data has become an active research area with many applications. These patterns can be hierarchical in nature, where a higher level pattern may consist of repetitions of lower level patterns. Unfortunately, the presence of noise may prevent these higher level patterns from being recognized in the sense that two portions (of a data sequence) that support the same (high level) pattern may have different layouts of occurrences of basic symbols. There may not exist any common representation in terms of raw symbol combinations; and hence such (high level) pattern may not be expressed by any previous model (defined on raw symbols or symbol combinations) and would not be properly recognized by any existing method. In this paper, we propose a novel model, namely meta-pattern, to capture these high level patterns. As a more flexible model, the number of potential meta-patterns could be very large. A substantial difficulty lies on how to identify the proper pattern candidates. However, the well-known Apriori property is not able to provide sufficient pruning power. A new property, namely component location property, is identified and used to conduct the candidate generation so that an efficient  computation-based mining algorithm can be developed. Last but not least, we apply our algorithm to some real and synthetic sequences and some interesting patterns are discovered. 1 
Infominer mining surprising periodic patterns.
lessoftheprobabilityofoccurrence.Amoresuitablemeathesensethateveryoccurrencecarriesthesameweightto- of5servers.Theworkloadoneachserverismeasured wardstheassessmentofthesignicanceofapatternregard by4ranks:low,relativelylow,relativelyhigh,andhigh. Thenthereare45=1024dierentevents,oneforeach surement,information,isintroducedtonaturallyvaluethe possiblecombinationofserverstates.Somepreliminary uousandmonotonicallydecreasingfunctionofitsprobabilitydegreeofsurpriseofeachoccurrenceofapatternasacontin- ofoccurrence.Thiswouldallowpatternswithvastlydierent occurrenceprobabilitiestobehandledseamlessly.Astheacoccuratamuchlowerfrequencythanotherstates,pat- examinationoftheclusterstatesovertimemightshow thatthestateuctuationcomplieswithsomeperiodic cumulateddegreeofsurpriseofallrepetitionsofapattern,thealldegreeofsurpriseofthepatternwithinadatasequence.conceptofinformationgainisproposedtomeasuretheovertemadministratorsiftheoccurrenceofsuchpattern(s)tern(s)involvingitmaybeofmoreintereststosomesys behavior.Althoughthehighworkloadonallserversmay Theboundedinformationgainpropertyisidentiedtotackle thepredicamentcausedbytheviolationofthedownwardclo- Earthquake.EarthquakesoccurveryofteninCalifornia. surepropertybytheinformationgainmeasureandinturn demonstratetheeciencyandtheusefulnessoftheproposed providesanecientsolutiontothisproblem.Empiricaltests maybeinterestedinknowingwhetherthereexistsany contradictsthepriorexpectation. inherentseismicperiodsothatpredictioncanbemade. Itcanbeclassiedbyitsmagnitudeandtype.Scientist model.
Dynamic Adaptive File Management in a Local Area Network.

Efficient mining of weighted association rules %28WAR%29.
In this paper, we extend the tradition association rule problem by allowing a weight to be associated with each item in a transaction, to reflect interest/intensity of the item within the transaction. This provides us in turn with an opportunity to associate a weight parameter with each item in the resulting association rule. We call it weighted association rule (WAR). WAR not only improves the confidence of the rules, but also provides a mechanism to do more effective target marketing by identifying or segmenting customers based on their potential degree of loyalty or volume of purchases. Our approach mines WARs by first ignoring the weight and finding the frequent itemsets (via a traditional frequent itemset discovery algorithm), and is followed by introducing the weight during the rule generation. It is shown by experimental results that our approach not only results in shorter average execution times, but also produces higher quality results than the generalization of previous known methods on quantitative association rules.
Mining asynchronous periodic patterns in time series data.
Periodicy detection in time series data is a challenging problem of great importance in many applications.
Collaborative Web caching based on proxy affinities.
With the exponential growth of hosts and traffic workloads on the Internet, collaborative web caching has been recognized as an efficient solution to alleviate web page server bottlenecks and reduce traffic. However, cache discovery, i.e., locating where a page is cached, is a challenging problem, especially in the fast growing World Wide Web environment, where the number of participating proxies can be very large. In this paper, we propose a new scheme which employs proxy affinities to maintain a dynamic distributed collaborative caching infrastructure. Web pages are partitioned into clusters according to proxy reference patterns. All proxies which frequently access some page(s) in the same web page cluster form an &#034;information group&#034;. When web pages belonging to a web page cluster are deleted from or added into a proxy&#039;s cache, only proxies in the associated information group are notified. This scheme can be shown to greatly reduce the number of messages and other overhead on individual proxies while maintaining a high cache hit rate. Finally, we employ trace driven simulation to evaluate our web caching scheme using three web access trace logs to verify that our caching structure can provide significant benefits on real workloads.
An Approach to Active Spatial Data Mining Based on Statistical Information.
Spatial data mining presents new challenges due to the large size of spatial data, the complexity of spatial data types, and the special nature of spatial access methods. Most research in this area has focused on efficient query processing of static data. This paper introduces an active spatial data mining approach that extends the current spatial data mining algorithms to efficiently support user-defined triggers on dynamically evolving spatial data. To exploit the locality of the effect of an update and the nature of spatial data, we employ a hierarchical structure with associated statistical information at the various levels of the hierarchy and decompose the user-defined trigger into a set of sub-triggers associated with cells in the hierarchy. Updates are suspendedin the hierarchy until their cumulative effect might cause the trigger to fire. It is shown that this approach achieves three orders of magnitude improvement over the naive approach that re-evaluate the condition over the database for each update, while both approaches produce the same result without any delay. Moreover, this scheme can support incremental query processing as well. 1
Mining Patterns in Long Sequential Data with Noise.

Dynamo design
Reliability at massive scale is one of the biggest challenges we face at Amazon.com, one of the largest e-commerce operations in the world; even the slightest outage has significant financial consequences and impacts customer trust. The Amazon.com platform, which provides services for many web sites worldwide, is implemented on top of an infrastructure of tens of thousands of servers and network components located in many datacenters around the world. At this scale, small and large components fail continuously and the way persistent state is managed in the face of these failures drives the reliability and scalability of the software systems.

This paper presents the design and implementation of Dynamo, a highly available key-value storage system that some of Amazon’s core services use to provide an “always-on ” experience. To achieve this level of availability, Dynamo sacrifices consistency under certain failure scenarios. It makes extensive use of object versioning and application-assisted conflict resolution in a manner that provides a novel interface for developers to use.
STING  An Approach to Active Spatial Data Mining.
Spatial data mining presents new challenges due to the large size of spatial data, the complexity of spatial data types, and the special nature of spatial access methods. Most research in this area has focused on efficient query processing of static data. This paper introduces an active spatial data mining approach which extends the current spatial data mining algorithms to efficiently support user-defined triggers on dynamically evolving spatial data. To exploit the locality of the effect of an update and the nature of spatial data, we employ a hierarchical structure with associated statistical information at the various levels of the hierarchy and decompose the user-defined trigger into a set of sub-triggers associated with cells in the hierarchy. Updates are suspended in the hierarchy until their cumulative effect might cause the trigger to fire. It is shown that this approach achieves three orders of magnitude improvement over the naive approach that re-evaluates the condition over...
PK%2Dtree A Spatial Index Structure for High Dimensional Point Data.
In this paper we present the PK-tree which is an index structure for high dimensional point data. The proposed indexing structure can be viewed as combining aspects of the PR-quad or K-D tree but where unnecessary nodes are eliminated. The unnecessary nodes are typically the result of skew in the point distribution and we show that by eliminating these nodes the performance of the resulting index is robust to skewed data distributions. The index structure is formally defined, efficiently updatable and bounds on the number of nodes and the mean height of the tree can be proved. Bounds on the expected height of the tree can be given under certain mild constraints on the spatial distribution of points. By appropriate choice of parameters the index structure can be allocated one node per page achieving acceptable storage utilization as well as low I/O counts per query. Empirical evidence both on real data sets and generated data sets with a range of distributions shows that the PK-tree out...
Structured Derivations of Consensus Algorithms for Failure Detectors.
In a seminal paper, Chandra and Toueg showed how unreliable failure detectors could allows processors to achieve consensus in asynchronous message passing systems. Since then, other researchers have developed consensus algorithms for other systems or based on different failure detectors. Each algorithm was developed and proven independently. This paper shows how a consensus algorithm for any of the standard models can be automatically converted to run in any other. These results show more clearly how the different system models and failure detectors can be related. In addition, they may permit the development of new results for new models also through transformations.  1 Introduction  The problem of achieving consensus among processors in a distributed system is fundamental in distributed computing. Unfortunately, consensus cannot be achieved in the presence of failures in completely asynchronous systems, either those with message passing [8,9] or those with shared memory [7,8,12]. Thi...
DynamO Dynamic Objects with Persistent Storage.

Mapping a Common Geoscientific Object Model to Heterogeneous Spatial Data Repositories.
Lately, a need to integrate specialized data management systems such as geographic information systems (GIS), or multimedia systems has gained importance [6]. A large variety of different data sets are available in various specialized repositories, and users would like to access and manipulate these data sets in a uniform way. Additionally, it is desirable to make the specialized  functionality provided by the individual repositories available to the user application through a homogeneous interface. At UCLA Data Mining Laboratory, we are developing geoPOM (geoscientific Persistent Object Manager), a heterogeneous geoscientific object system which provides a homogeneous interface to heterogeneous spatial data repositories [20]. geoPOM provides an object-oriented spatial data model for the definition of user-defined spatial object types. Internally, geoPOM maps user-defined spatial object types to different specialized spatial data repositories, and employs their storage, search and spat...
